#include "linearList.h"
#include <iostream>
using namespace std;

sequenceList::sequenceList(const int& maxSize, const int& size, float arr[]) {
    if (size > maxSize) {
        printf("超出最大容量，初始化失败\n");
        return;
    }

    maxCapcity = maxSize;
    curNumberOfItem = size;
    myList = new float[maxSize];

    if (arr != NULL) {
        for (int i = 0; i < size; i++) {
            myList[i] = arr[i];
        }
    }
}

sequenceList::~sequenceList() {
    delete[] myList;
}

bool sequenceList::addItem(const float& item) {
    if (curNumberOfItem >= maxCapcity) {
        return false;
    }

    myList[curNumberOfItem] = item;

    curNumberOfItem++;

    return true;
}

bool sequenceList::insertItem(const int& index, const float& item) {
    if (index < 0 || index > curNumberOfItem) {
        printf("下标参数不合法\n");
        return false;
    }

    if (curNumberOfItem >= maxCapcity) {
        printf("容量不足，添加失败\n");
        return false;
    }

    for (int i = curNumberOfItem; i > index; i--) {
        myList[i] = myList[i - 1];
    }

    myList[index] = item;
    curNumberOfItem++;

    return true;
}

int sequenceList::deleteItem(const float& item) {
    for (int i = 0; i < curNumberOfItem; i++) {
        if (myList[i] == item) {
            for (int j = i; j < curNumberOfItem - 1; j++) {
                myList[j] = myList[j + 1];
            }

            curNumberOfItem--;
            return i;
        }
    }

    return -1;
}

bool sequenceList::locate(const int& index, float& value) {
    if (index < 0 || index >= curNumberOfItem) {
        return false;
    }

    value = myList[index];
    return true;
}

int sequenceList::locate(const float& item) {
    for (int i = 0; i < curNumberOfItem; i++) {
        if (myList[i] == item) {
            return i;
        }
    }

    return -1;
}

void sequenceList::reverse() {
    for (int i = 0; i < curNumberOfItem / 2; i++) {
        swap(myList[i], myList[curNumberOfItem - 1 - i]);
    }
}

void sequenceList::print()
{
    cout << curNumberOfItem << ":";

    for(int i = 0; i < curNumberOfItem-1; i++)
    {
        cout << myList[i] << ",";
    }

    cout << myList[curNumberOfItem-1] << endl;
}

listNode::listNode(float nodeData, listNode* succ) {
    data = nodeData;
    next = succ;
}

listNode::~listNode() {
}

linkList::linkList() {
    firstNode = new listNode(0);
    lastNode = firstNode;
    curNode = firstNode;
    listSize = 0;
}


linkList::linkList(const int& size, float arr[]) {
    firstNode = new listNode(0);
    lastNode = firstNode;
    curNode = firstNode;
    listSize = 0;

    if (arr != NULL) {
        for (int i = 0; i < size; i++) {
            tailInsertItem(arr[i]);
        }
    }
}

linkList::~linkList() {
    listNode* current = firstNode;

    while (current != NULL) {
        listNode* next = current->next;
        delete current;
        current = next;
    }
}

bool linkList::headInsertItem(const float& item) {
    listNode* newNode = new listNode(item, firstNode->next);
    if (newNode == NULL) {
        return false;
    }

    firstNode->next = newNode;

    if (lastNode == firstNode) {
        lastNode = newNode;
    }
    listSize++;

    return true;
}

bool linkList::tailInsertItem(const float& item) {
    listNode* newNode = new listNode(item);
    if (newNode == NULL) {
        return false;
    }

    
    lastNode->next = newNode;
    lastNode = newNode;

    listSize++;

    return true;
}

int linkList::insertItem(const int& index, const float& item) {
    if (index < 0 || index > listSize) {
        return -1;
    }

    if (index == 0) {
        return headInsertItem(item) ? 0 : -1;
    }

    if (index == listSize) {
        return tailInsertItem(item) ? index : -1;
    }

    listNode* current = firstNode;
    for (int i = 0; i < index; i++) {
        current = current->next;
    }

    listNode* newNode = new listNode(item, current->next);
    if (newNode == NULL) {
        return -1;
    }

    current->next = newNode;
    listSize++;

    return index;
}

int linkList::deleteItem(const float& item) {
    listNode* current = firstNode->next;
    listNode* prev = firstNode;
    int index = 0;

    while (current != NULL) {
        if (current->data == item) {
           
            prev->next = current->next;
            if (current == lastNode) {
                lastNode = prev;
            }

            delete current;
            listSize--;

            return index;
        }

        prev = current;
        current = current->next;
        index++;
    }

    return -1;
}

bool linkList::locate(const int& index, float& value) {
    if (index < 0 || index >= listSize) {
        return false;
    }

    listNode* current = firstNode->next;
    for (int i = 0; i < index; i++) {
        current = current->next;
    }

    value = current->data;

    return true;
}

int linkList::locate(const float& item) {
    listNode* current = firstNode->next;
    int index = 0;

    while (current != NULL) {
        if (current->data == item) {
            return index;
        }

        current = current->next;
        index++;
    }

    return -1;
}

void linkList::ascendingOrder() {
    if (listSize <= 1) {
        return;
    }

    for (listNode* i = firstNode->next; i->next != NULL; i = i->next) {
        listNode* j = firstNode->next;
        while (j->next != NULL) {
            if (j->data > j->next->data) {
                swap(j->data, j->next->data);
            }
            j = j->next;
        }
    }
}

void linkList::reverse() {
    if (listSize <= 1) {
        return;
    }

    listNode* prev = NULL;
    listNode* current = firstNode->next;
    listNode* next = NULL;

    lastNode = current;

    while (current != NULL) {
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }

    firstNode->next = prev;
}

void linkList::print()
{
    curNode = firstNode;

    cout << listSize << ":";

    while(curNode != lastNode)
    {
        if(curNode->next == lastNode)
            cout << curNode->next->data << endl;
        else
        {
            cout << curNode->next->data << ",";
        }
        
        
        curNode = curNode->next;
    }
}

void linkList::clear() {
    listNode* current = firstNode->next;
    while (current != NULL) {
        listNode* next = current->next;
        delete current;
        current = next;
    }

    firstNode->next = NULL;
    curNode = firstNode;
    lastNode = firstNode;
    listSize = 0;
}

void merge(linkList& list1, linkList& list2) {
    list1.ascendingOrder();
    list2.ascendingOrder();

    listNode* node1 = list1.getFirstNode()->next;
    listNode* node2 = list2.getFirstNode()->next;

    listNode* newFirstNode = new listNode(0);
    listNode* newLastNode = NULL;

    while (node1 != NULL && node2 != NULL) {
        if (node1->data < node2->data) {
            listNode* newNode = new listNode(node1->data, newFirstNode->next);
            newFirstNode->next = newNode;           

            if (newLastNode == NULL) {
                newLastNode = newNode;
            }

            node1 = node1->next;
        }
        else {
            listNode* newNode = new listNode(node2->data, newFirstNode->next);
            newFirstNode->next = newNode;

            if (newLastNode == NULL) {
                newLastNode = newNode;
            }

            node2 = node2->next;
        }
    }

    while (node1 != NULL) {
        listNode* newNode = new listNode(node1->data, newFirstNode->next);
        newFirstNode->next = newNode;

        if (newLastNode == NULL) {
            newLastNode = newNode;
        }

        node1 = node1->next;
    }

    while (node2 != NULL) {
        listNode* newNode = new listNode(node2->data, newFirstNode->next);
        newFirstNode->next = newNode;

        if (newLastNode == NULL) {
            newLastNode = newNode;
        }

        node2 = node2->next;
    }

    int newSize = list1.getListSize() + list2.getListSize();

    list1.clear();
    list1.setFirstDataNode(newFirstNode->next);
    list1.setLastNode(newLastNode);
    list1.setListSize(newSize);
    
    delete newFirstNode;
    
    return;
}